class Solution
{
public:
    vector<int> getCoprimes(vector<int> &nums, vector<vector<int>> &edges)
    {
        int n = nums.size();
        int M = *max_element(nums.begin(), nums.end());
        vector<vector<int>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<vector<pair<int, int>>> numNodes(M + 1);
        vector<int> ans(n, -1);

        function<void(int, int, int)> dfs = [&](int node, int parent, int depth)
        {
            int val = nums[node];
            int ansDepth = -1;
            for (int parentVal = 1; parentVal <= M; ++parentVal)
            {
                if (numNodes[parentVal].empty() || gcd(val, parentVal) != 1)
                {
                    continue;
                }
                auto [parentNode, parentDepth] = numNodes[parentVal].back();
                if (parentDepth > ansDepth)
                {
                    ansDepth = parentDepth;
                    ans[node] = parentNode;
                }
            }

            numNodes[val].push_back({node, depth});
            for (auto next : graph[node])
            {
                if (next != parent)
                {
                    dfs(next, node, depth + 1);
                }
            }
            numNodes[val].pop_back();
        };
        dfs(0, -1, 0);
        return ans;
    }
};